The Twofish Encryption Algorithm: A 128-Bit Block Cipher The Twofish Encryption Algorithm: A 128-Bit Block Cipher
by Bruce Schneier ; John Kelsey ; Doug Whiting ; David Wagner ; Chris Hall ; Niels Ferguson
Wiley Computer Publishing, John Wiley & Sons, Inc.
ISBN: 0471353817   Pub Date: 03/01/99
  

Previous Table of Contents Next


9.4.10 Conclusion

For practical purposes, Twofish is immune to differential cryptanalysis. We have shown that any 12-round differential has a probability of at most 2-102.8. This bound is far from tight, and we expect that any real differential has a much smaller probability.

The Twofish structure is not easy to analyze. The mixing of various operations makes it hard to give a clean analysis and forces us to use approximation techniques. Some aspects, such as the rotates, make the analysis a lot harder and force us to use less accurate approximations, while there is no a priori reason to assume that the rotations would have any significant influence on the differential probabilities.

One can argue whether a cipher with a structure that is easier to analyze would be preferable. On the one hand, a structure that allows easier analysis makes it easier to rule out certain attacks. On the other hand, the very structure that makes it easy to analyze might be used in a future attack. Although differential attacks were obviously considered during the design, Twofish was not specifically strengthened against differential attacks, or designed to allow a simple upper bound on differential probabilities to be derived. This is a result of the design philosophy of Twofish. It was not optimized specifically against known attacks; it is a conservative design that tries to resist both known and unknown attacks.

9.5 Linear Cryptanalysis

We perform a similar analysis to that of Section 9.4 in the context of linear cryptanalysis. The approach is the same, but a simpler model was used.

Our model is much as before: it is centered around the pattern of active bytes. (Here a byte position is considered active if any of its bits are active in the linear approximation for that round; i.e., if the mask T selects at least one bit from that byte position.) We used a fairly rough approximation of the effect of the PHT. This approximation fails to accurately treat some low-probability approximations for the PHT where there are fewer active bytes at the output than at the input. This analysis also ignores the 1-bit rotations.

Because of the second limitation, our model should be considered only a heuristic; it may fail to capture some important features of the round function.

A search for the best linear characteristics within this model found that every 12-round characteristic has at least 36 active S-boxes. Here is an example of one characteristic we found:

1  FE->FF (1 active)
2  FF<-FF (2 active)
3  FF->DD (4 active)
4  CC<-DD (6 active)
5  CC->00 (0 active)
6  C<-00  (6 active)
7  CC->77 (4 active)
8  00<-77 (0 active)
9  00->77 (4 active)
10 66<-77 (6 active)
11 66->00 (0 active)
12 66<-00 (3 active)
13 66 07

The first few approximations for the F function are 0116FF16, FF16, 2216FF16, 3316DD16, and so on.

To translate these results into an estimated attack complexity, we turn to the results of Section 7.2.3. We have LPmax ≤ (108/256)2, so this suggests an attacker would need at least (LPmax)-36 ≈ 289.6 known plaintexts; and such an analysis would only work for a very small class of weak keys (representing about 2-49.1 of the keyspace for 128-bit keys, or about 2-68 of the 192-bit keyspace).

It is much more natural to demand that the attack work for a significant percentage of all keys. In this case, LPmax = (80/256)2 is a much more representative value, and thus in this model any linear attack working for a significant fraction of the keyspace would require at least 2120.8 chosen plaintexts.

These results are only heuristic estimates, and probably overestimate the probability of the best linear characteristic. Nonetheless, they present some useful evidence for the security of Twofish against linear cryptanalysis.

A more thorough analysis along the lines of section 9.4 remains to be performed.

9.5.1 Multiple Linear Approximations

Multiple linear approximations [KR94, KR95] allow one to combine the bias of several high-probability linear approximations. However, it only provides a significant advantage over traditional linear cryptanalysis when there are a number of linear approximations whose bias is close to that of the best linear approximation. In practice, this seems to improve linear attacks by a small constant factor. Hence, we do not feel that Twofish is vulnerable to this kind of cryptanalysis.

9.5.2 Non-linear Cryptanalysis

Another generalization of linear cryptanalysis looks at non-linear relations [KR96b], e.g., quadratic relations. While this attack, combined with the technique of multiple approximations [KR94], managed to improve the best linear attack against DES a minute amount [SK98], we do not believe it can be brought to bear against Twofish for the same reasons that it is immune to linear cryptanalysis.

9.5.3 Generalized Linear Cryptanalysis

This generalization of linear cryptanalysis uses the notion of binary I/O sums [HKM95, Har96, JH96]. An attacker attempts to find a statistical imbalance that can be described as the result of some group operation on some function of the plaintext and some function of the ciphertext. We have not found any such statistical imbalances, and believe Twofish to be immune to this kind of analysis.

9.5.4 Partitioning Cryptanalysis

Partitioning cryptanalysis is another generalization of linear cryptanalysis [Har96, JH96, HM97].3. An attacker trying to carry out a partitioning attack is generally trying to find some way of partitioning the input and output spaces of the round function so that knowledge of which partition the input to a round is in gives some information about which partition the output from a round is in. This can be seen as a general form of a failure of the block cipher to get good confusion; an attacker after N rounds can distinguish the output from the Nth round from a random block of bits, because the output is somewhat more likely to be in one specific partition than in any of the others. This can be used in a straightforward way to attack the last round of the cipher.4


3Similar ideas can be found in [Vau96b]
4Basic results against reduced-round DES can be found in [HYSK98].

We have been unable to find any useful way to partition the input and output spaces of the Twofish F function or a Twofish round that works consistently across many keys, because of the key-dependent S-boxes. For the 128-bit key case, there are 264 different F functions, presumably each with its own most useful partitioning. We are not aware of any general way to partition F’s inputs and outputs to facilitate such attacks.

9.5.5 Differential-linear Cryptanalysis

Differential-linear cryptanalysis uses a combination of techniques from both differential and linear cryptanalysis [LH94]. Due to the need to cover the last part of the cipher with two copies of a linear characteristic, the bias of the linear characteristic is likely to be extremely small unless the linear portion of the attack is confined to just three or four rounds. (The available linear characteristics for Twofish’s round function have a relatively low probability, and are very hard to combine due to the MDS and PHT mappings.) This means that the cryptanalyst would need to cover almost all of the rounds with the differential characteristic, making a differential-linear analysis not much more powerful than a purely differential analysis. Therefore, we feel that differential-linear cryptanalysis is unlikely to be successful against the Twofish structure. In our analysis, we have found no differential-linear attacks that work against Twofish.

9.6 Interpolation Attack

The interpolation attack [JK97, MSK98b] is effective against ciphers that use simple algebraic functions. The principle of the attack is simple: if the ciphertext can be represented as a polynomial or rational expression (with N coefficients) of the plaintext, then the polynomial or rational expression can be reconstructed using N plaintext/ciphertext pairs.

However, interpolation attacks are often only workable against ciphers with a very small number of rounds, or against ciphers whose round functions have very low algebraic degree. Twofish’s S-boxes already have relatively large algebraic degree, and the combination of operations from different algebraic groups (including both addition mod 232 and XOR) should help increase the degree even further. Therefore, we believe that Twofish is secure against interpolation attacks after even only a small number of rounds.


Previous Table of Contents Next